class MedianFinder {
public:
    MedianFinder() {

    }
    
    void addNum(int num) {
        // 保持大根堆存小的数据，小根堆存大的数据
        // 比如：[1, 2, 3][4, 5, 6]
        //          大根     小根
        // 这样的话堆顶分别就是3和4，当然这是n是偶数的情况(n是两个堆的元素总个数)
        // 比如现在n是偶数，我想插入一个数，比如是5
        // 1. 先插入小根堆中，此时小根堆就是[4, 5, 5, 6]，大堆就还是[1, 2, 3]
        // 2. 再把小根堆堆顶数据移到大堆，此时大堆就是[1, 2, 3, 4]了，小堆就是[5, 5, 6]
        // 此时如果想要查中位数，那就直接返回大堆堆顶的数就ok了(此时n是奇数)

        // 比如现在n是奇数，我想插入一个数，比如是2
        // 1. 先插入大根堆中，此时大根堆就是[1, 2, 2, 3, 4]，小堆就还是[5, 5, 6]
        // 2. 再把大根堆堆顶数据移到小堆，此时大堆就是[1, 2, 2, 3]了，小堆就是[4, 5, 5, 6]
        // 此时如果想要查中位数，那就直接返回大堆堆顶和小堆堆顶的数加起来除以2就ok了(此时n是偶数)

        // 或者这样想，当n是奇数时，说明有一个堆是数据较少的，因为我们控制大堆堆顶是中位数，这样大堆就比小堆多一个数(当n是奇数时)
        // 此时这个数无论是多大，如果是目前最大的(站在上帝视角看的话)，此时先插入到大堆，那么必定会在大堆的堆顶处
        int n1 = _big.size();
        int n2 = _small.size();
        if(n1 != n2)
        {
            // n是奇数，说明大堆中的数比小堆多了一个
            // 此时还是先push进大堆
            // 然后重新选一个最大的数放到小堆
            _big.push(num);
            _small.push(_big.top());
            _big.pop();
        }
        else if(n1 == n2)   
        {
            // n是偶数
            // 说明大堆小堆的数据个数是一样的
            // 此时先push进小堆
            // 然后重新选一个最小的数放在大堆
            // 而这个数肯定是在大堆中最小的，会在堆顶，此时如果获取中位数，那这个数就是中位数了
            _small.push(num);
            _big.push(_small.top());
            _small.pop();
        }
    }
    
    double findMedian() {
        int n1 = _big.size();
        int n2 = _small.size();
        if(n1 == n2)        // n是偶数
            return (_big.top() + _small.top()) / 2.0;
        else
            return (double)_big.top();
    }
private:
    priority_queue<int> _big;       // 大根堆
    priority_queue<int, vector<int>, greater<int>> _small;  // 小根堆
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */